This invention relates to an image processing method and, more particularly, to a method for extracting features of a picture element (PEL) array pattern by means of software.
In pattern recognition such as optical character recognition, various features of patterns to be recognized have been extracted for use in classification of the patterns such as characters based on these features. For example, T. Kawatani, xe2x80x9cHandprinted Numerals Recognition by Learning Distance Function,xe2x80x9d The Transactions of the Institute of Electronics, Information and Communication Engineers, September 1993, Vol. J76-D-2, No. 9, pp. 1851-1859 (in Japanese) discloses a technique adapted for determining attributes of a point on a contour in a PEL array pattern, such as a designation of concavity/convexity of the point indicating whether it is concave or convex, a direction of the concavity/convexity and a strength of the concavity/convexity (acuteness), whereby they may be utilized for calculating feature values of the PEL array pattern.
In this prior technique, however, a tangent line direction of a point of interest on a contour is simply regarded as a direction of the concavity/convexity of its contour portion, without giving any attribute of direction to a portion that has strong acuteness. While this prior technique enables to obtain a stable value for a direction of the concavity/convexity at a portion where a contour shape is approximate to a straight line as shown in FIG. 16, this does not apply to a portion where a contour shape has a strong curvature as shown in FIG. 17. This is because, in the illustrated situation, a slight positional change of a center point will cause a direction of the concavity/convexity to be radically changed, which will in turn result in an excessive variation of feature values to be extracted from a PEL array pattern. Thus, what has been needed in this technical field is a novel scheme that is capable of extracting features in a more stable manner.
Japanese Patent Publication No. 6-19551 (corresponding to U.S. Pat. No. 5,590,220), assigned to the present assignee, discloses a technique adapted for determining attributes of bending points (identified by the letters xe2x80x9caxe2x80x9d through xe2x80x9cgxe2x80x9d in FIG. 18) on a contour in a PEL array pattern, such as a designation of concavity/convexity of a bending point of interest indicating whether it is concave or convex, a direction of the concavity/convexity and a strength of the concavity/convexity (acuteness) as shown in FIG. 19, whereby they may be utilized for calculating feature values of the PEL array pattern.
According to this prior technique, a direction of the concavity/convexity is calculated solely at a portion where a contour shape has a strong curvature as shown in FIG. 18 and, thus, it avoids said problem of an excessive variation of feature values to be extracted from a PEL array pattern. Nevertheless, this prior technique requires further processing such as dividing contour groups at each of the selected bending points and, hence, it eventually requires a large amount of calculation time for extracting a sufficient quantity of feature values to be used in pattern recognition. Further, this prior technique entails difficulty in taking a strong convexity or concavity in the graphic of xe2x80x9c0xe2x80x9d and/or xe2x80x9c0xe2x80x9d that is approximate to a circle, thereby causing an occurrence position of a feature value to be unstable.
It is, therefore, an object of this invention to provide an image recognition system that is capable of deriving stable feature values, without depending on a contour shape of a graphic.
It is another object of this invention to quickly extract a sufficient amount of feature values for use in effective pattern (character and/or graphic) recognition of high recognition rates.
In accordance with this invention, one or more contours of a PEL array pattern are detected and, then, a strength of concavity/convexity on each contour (acuteness) and a direction of the concavity/convexity are determined. Using an acuteness value of a contour point of interest, its curvature is classified into a group of strong curvatures or another group of weak curvatures such that the definition of a direction of the concavity/convexity (contour direction) is appropriately switched from one to another for calculation. In a preferred aspect of this invention, using an acuteness value of a contour point of interest, its contour curvature is classified into either one of five curvature groups, comprising xe2x80x9cstrong concavity,xe2x80x9d xe2x80x9cweak concavity,xe2x80x9d xe2x80x9cstraight line/inflection point,xe2x80x9d xe2x80x9cweak convexity,xe2x80x9d and xe2x80x9cstrong convexity.xe2x80x9d If its contour curvature is classified into either xe2x80x9cstrong concavityxe2x80x9d or xe2x80x9cstrong convexity,xe2x80x9d then calculation of a normal line direction will be made for deriving a contour direction. On the other hand, if its contour curvature is classified into xe2x80x9cstraight line/inflection point,xe2x80x9d then calculation of a tangent line direction will be made. In so doing, it is possible to improve image recognition rates as compared to those of the prior schemes utilizing conventional feature values.
In accordance with one aspect of this invention, there is provided a method for analyzing one or more contours detected from a picture element (PEL) array pattern and extracting feature values of the PEL array pattern, comprising the steps of:
(a) tracing the contours of said PEL array pattern and generating a list of a plurality of contour points that exist on each traced contour;
(b) calculating, for one of said plurality of contour points, an acuteness value representing a contour curvature;
(c) if said acuteness value indicates an acute curve, then using a first calculation equation to calculate a contour direction of said one contour point, and if said acuteness value indicates a straight line or an inflection point, then using a second calculation equation other than the first calculation equation to calculate a contour direction of said one contour point; and
(d) outputting a feature value based on the contour direction of said one contour point.
Note that, in the claims of the present specification, the expression of xe2x80x9cfirst calculation equationxe2x80x9d represents a concept covering any equation adapted for calculating a direction that is approximate to a normal line or another direction calculated therefrom, such as a direction of a straight line connecting a contour point of interest and a midpoint between an Nth previous point and an Nth (or Mth) following point of the contour point of interest, as described below for a preferred embodiment. Similarly, the expression xe2x80x9csecond calculation equationxe2x80x9d represents a concept covering any equation adapted for calculating a direction that is approximate to a tangent line or another direction calculated therefrom, such as a direction of a straight line connecting the Nth previous point and Nth (or Mth) following point of the contour point of interest, as described below for a preferred embodiment.
In accordance with another aspect of this invention, there is provided a feature extraction method, wherein said first calculation equation makes a calculation based on coordinate values of said one contour point Pi, coordinate values of an Nth previous point Pixe2x88x92N and coordinate values of an Nth following point Pi+N of said one contour point, and wherein said second calculation equation makes a calculation based on the coordinate values of the Nth previous point Pixe2x88x92N and the coordinate values of the Nth following point Pi+N of said one contour point.
In accordance with another aspect of this invention, there is provided a method for analyzing one or more contours detected from a picture element (PEL) array pattern and extracting feature values of the PEL array pattern, comprising the steps of:
(a) tracing the contours of said PEL array pattern and generating a list of a plurality of contour points that exist on each traced contour;
(b) calculating, for one contour point Pi among said plurality of contour points, an acuteness value representing a contour curvature;
(c) based on the calculated acuteness value, determining either one of curvature groups, comprising xe2x80x9cstrong concavity,xe2x80x9d xe2x80x9cweak concavity,xe2x80x9d xe2x80x9cstraight line/inflection point,xe2x80x9d xe2x80x9cweak convexityxe2x80x9d and xe2x80x9cstrong convexity,xe2x80x9d in which the contour curvature of said one contour point Pi falls;
(d) if the contour curvature of said one contour point Pi is determined to fall in either xe2x80x9cstrong concavityxe2x80x9d or xe2x80x9cstrong convexity,xe2x80x9d then determining a contour direction based on a direction of a straight line connecting said one contour point Pi and a midpoint between an Nth previous point Pixe2x88x92N and an Nth following point Pi+N of said one contour point, and if the contour curvature of said one contour point Pi is determined to fall in xe2x80x9cstraight line/inflection point,xe2x80x9d then determining a contour direction based on a direction of a straight line connecting said Nth previous point Pixe2x88x92N and Nth following point Pi+N; and
(e) outputting a feature value based on the contour direction of said one contour point.
In accordance with another aspect of this invention, there is provided an apparatus for analyzing one or more contours detected from a picture element (PEL) array pattern and extracting feature values of the PEL array pattern, comprising:
(a) image input means for capturing said PEL array pattern;
(b) an X-Y list, created by tracing the contours of said PEL array pattern, for controlling coordinate values of a contour point that exists on each traced contour;
(c) an acuteness list, created by calculating an acuteness value representing a contour curvature of said contour point;
(d) a contour direction list, created by using either a first calculation equation if said acuteness value indicates an acute curve, and by using a second calculation equation other than the first calculation equation if said acuteness value indicates a straight line or an inflection point; and
(e) means for outputting a feature value based on said contour direction list.
In accordance with another aspect of this invention, there is provided a computer readable storage medium for storing a program that is arranged to analyze one or more contours detected from a picture element (PEL) array pattern and to extract feature values of the PEL array pattern, said program comprising:
(a) program code means for causing said computer to trace the contours of said PEL array pattern and to generate a list of a plurality of contour points that exist on each traced contour;
(b) program code means for causing said computer to calculate, for one of said plurality of contour points, an acuteness value representing a contour curvature;
(c) program code means for causing said computer to use a first calculation equation to calculate a contour direction of said one contour point if said acuteness value indicates an acute curve, and to use a second calculation equation other than the first calculation equation to calculate a contour direction of said one contour point if said acuteness value indicates a straight line or an inflection point; and
(d) program code means for causing said computer to output a feature value based on the contour direction of said one contour point.
In accordance with another aspect of this invention, there is provided a storage medium, wherein said first calculation equation makes a calculation based on coordinate values of said one contour point Pi, coordinate values of an Nth previous point Pixe2x88x92N and coordinate values of an Nth following point Pi+N of said one contour point, and wherein said second calculation equation makes a calculation based on the coordinate values of the Nth previous point Pixe2x88x92N and the coordinate values of the Nth following point Pi+N of said one contour point.
In accordance with another aspect of this invention, there is provided a computer readable storage medium for storing a program that is arranged to analyze one or more contours detected from a picture element (PEL) array pattern and to extract feature values of the PEL array pattern, said program comprising:
(a) program code means for causing said computer to trace the contours of said PEL array pattern and to generate a list of a plurality of contour points that exist on each traced contour;
(b) program code means for causing said computer to calculate, for one contour point Pi among said plurality of contour points, an acuteness value representing a contour curvature;
(c) program code means for causing said computer to determine, based on the calculated acuteness value, either one of curvature groups, comprising xe2x80x9cstrong concavity,xe2x80x9d xe2x80x9cweak concavity,xe2x80x9d xe2x80x9cstraight line/inflection point,xe2x80x9d xe2x80x9cweak convexityxe2x80x9d and xe2x80x9cstrong convexity,xe2x80x9d in which the contour curvature of said one contour point Pi falls;
(d) program code means for causing said computer to determine a contour direction based on a direction of a straight line connecting said one contour point Pi and a midpoint between an Nth previous point Pixe2x88x92N and an Nth following point Pi+N of said one contour point if the contour curvature of said one contour point Pi is determined to fall in either xe2x80x9cstrong concavityxe2x80x9d or xe2x80x9cstrong convexity,xe2x80x9d and to determine a contour direction based on a direction of a straight line connecting said Nth previous point Pixe2x88x92N and Nth following point Pi+N if the contour curvature of said one contour point Pi is determined to fall in xe2x80x9cstraight line/inflection point;xe2x80x9d and
(e) program code means for causing said computer to output a feature value based on the contour direction of said one contour point.